package com.hainiu.cat.sort.write;

/**
 * create by biji.zhao on 2021/5/31
 */
public class Test {


    public static void main(String[] args) {
        LinkNode one = new LinkNode(1);

        LinkNode two = new LinkNode(2);
        one.setNext(two);

        LinkNode three = new LinkNode(3);
        two.setNext(three);

        LinkNode four = new LinkNode(4);
        three.setNext(four);

        LinkNode five = new LinkNode(5);
        four.setNext(five);

        LinkNode six = new LinkNode(6);
        five.setNext(six);

        one = execute(one, 2, 4);

        System.out.println("===========");
    }

    // 给定一个链表的头节点，把从第m个节点到第n个节点反转
    private static LinkNode execute(LinkNode start, int m, int n) {
        if (n < m || n < 0 || m < 0) {
            return start;
        }
        // 拼接上需要反转的部分
        LinkNode newNode = subLinkNode(0, m, start);

        LinkNode needRevertLink = subLinkNode(m, n, start);
        newNode.setNext(revert(needRevertLink));

        LinkNode linkNode = subLinkNode(n, null, start);
        // 再拼接上不需要反转的部分
        newNode.setNext(linkNode);
        return newNode;
    }

    private static LinkNode subLinkNode(int m, Integer n, LinkNode oldNode) {
        int j = 0;
        LinkNode linkNode = oldNode;
        linkNode.setNext(oldNode.getNext());
        LinkNode nextNode = linkNode.getNext();
        while (oldNode.getNext() != null) {
            if (n != null && j >= n && j < m) {
                break;
            }
            oldNode = oldNode.getNext();
            nextNode.setNext(oldNode.getNext());
            nextNode = nextNode.getNext();
            j ++ ;
        }
        return linkNode;
    }

    private static class LinkNode{
        private int data;
        private LinkNode next;

        public int getData() {
            return data;
        }

        public void setData(int data) {
            this.data = data;
        }

        public LinkNode getNext() {
            return next;
        }

        public void setNext(LinkNode next) {
            this.next = next;
        }

        public LinkNode(int data) {
            this.data = data;
        }
    }

    /**
     * 反转
     * @param curr
     * @return
     */
    private static LinkNode revert(LinkNode curr) {
        if (curr == null || curr.getNext() == null) {
            return curr;
        }
        LinkNode reHead = revert(curr.getNext());
        curr.getNext().setNext(curr);
        curr.setNext(null);
        return reHead;
    }


}
